<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>动态规划：背包问题详解</title>
    <link href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css" rel="stylesheet">
    <link href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css" rel="stylesheet">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", 
                        "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
            background-color: #f8f9fa;
            color: #333;
        }
        .hero-gradient {
            background: linear-gradient(135deg, #6B73FF 0%, #000DFF 100%);
        }
        .code-block {
            background-color: #2d2d2d;
            border-radius: 8px;
            color: #f8f8f2;
        }
        .dp-card {
            transition: transform 0.3s ease, box-shadow 0.3s ease;
        }
        .dp-card:hover {
            transform: translateY(-5px);
            box-shadow: 0 20px 25px -5px rgba(0, 0, 0, 0.1), 0 10px 10px -5px rgba(0, 0, 0, 0.04);
        }
        .highlight-text {
            background: linear-gradient(90deg, #6B73FF 0%, #000DFF 100%);
            -webkit-background-clip: text;
            background-clip: text;
            color: transparent;
        }
        .first-letter:first-letter {
            float: left;
            font-size: 4rem;
            line-height: 0.8;
            margin: 0.1em 0.2em 0 0;
            color: #6B73FF;
        }
    </style>
</head>
<body class="antialiased">
    <!-- Hero Section -->
    <section class="hero-gradient text-white py-20 px-4 md:px-0">
        <div class="container mx-auto max-w-5xl">
            <div class="flex flex-col md:flex-row items-center">
                <div class="md:w-1/2 mb-10 md:mb-0">
                    <h1 class="text-4xl md:text-5xl font-bold mb-4 font-serif">背包问题</h1>
                    <p class="text-xl md:text-2xl mb-6 opacity-90">动态规划的经典应用</p>
                    <p class="text-lg opacity-80 mb-8 first-letter">
                        背包问题是计算机科学中经典的优化问题，它展示了动态规划如何有效地解决看似复杂的问题。
                        通过将问题分解为子问题并存储中间结果，我们可以避免重复计算，大大提高算法效率。
                    </p>
                    <div class="flex items-center space-x-4">
                        <div class="flex items-center">
                            <i class="fas fa-code-branch mr-2 text-yellow-300"></i>
                            <span>动态规划</span>
                        </div>
                        <div class="flex items-center">
                            <i class="fas fa-clock mr-2 text-yellow-300"></i>
                            <span>O(n*w)时间复杂度</span>
                        </div>
                    </div>
                </div>
                <div class="md:w-1/2 flex justify-center">
                    <div class="relative">
                        <div class="w-64 h-64 bg-white bg-opacity-20 rounded-full absolute -top-4 -left-4"></div>
                        <div class="w-64 h-64 bg-white bg-opacity-10 rounded-full absolute -bottom-4 -right-4"></div>
                        <div class="relative z-10 p-6 bg-white bg-opacity-10 backdrop-filter backdrop-blur-lg rounded-2xl border border-white border-opacity-20 shadow-xl">
                            <h3 class="text-xl font-bold mb-4">示例题目</h3>
                            <div class="space-y-3">
                                <div class="flex">
                                    <div class="w-1/2 text-gray-300">物品重量:</div>
                                    <div class="w-1/2 font-mono">[1, 3, 4]</div>
                                </div>
                                <div class="flex">
                                    <div class="w-1/2 text-gray-300">物品价值:</div>
                                    <div class="w-1/2 font-mono">[15, 20, 30]</div>
                                </div>
                                <div class="flex">
                                    <div class="w-1/2 text-gray-300">背包容量:</div>
                                    <div class="w-1/2 font-mono">4</div>
                                </div>
                                <div class="pt-2 mt-4 border-t border-white border-opacity-20">
                                    <div class="flex">
                                        <div class="w-1/2 text-gray-300">最优解:</div>
                                        <div class="w-1/2 font-bold text-yellow-300">35</div>
                                    </div>
                                </div>
                            </div>
                        </div>
                    </div>
                </div>
            </div>
        </div>
    </section>

    <!-- Main Content -->
    <section class="py-16 px-4 md:px-0">
        <div class="container mx-auto max-w-5xl">
            <!-- Problem Definition -->
            <div class="bg-white rounded-xl shadow-md overflow-hidden mb-12 dp-card">
                <div class="p-6 md:p-8">
                    <div class="flex items-center mb-6">
                        <div class="w-12 h-12 bg-blue-100 rounded-full flex items-center justify-center mr-4">
                            <i class="fas fa-question-circle text-blue-600 text-xl"></i>
                        </div>
                        <h2 class="text-2xl font-bold text-gray-800">问题描述</h2>
                    </div>
                    <p class="text-gray-700 mb-4 leading-relaxed">
                        有 <span class="font-bold text-blue-600">n</span> 件物品和一个最多能背重量为 <span class="font-bold text-blue-600">w</span> 的背包。
                        第 <span class="font-bold text-blue-600">i</span> 件物品的重量是 <span class="font-bold text-blue-600">weight[i]</span>，
                        价值是 <span class="font-bold text-blue-600">value[i]</span>。
                        每件物品只能使用一次，求解将哪些物品装入背包可使价值总和最大。
                    </p>
                    <div class="bg-blue-50 border-l-4 border-blue-500 p-4 mt-6 rounded-r">
                        <div class="flex">
                            <div class="flex-shrink-0">
                                <i class="fas fa-info-circle text-blue-500"></i>
                            </div>
                            <div class="ml-3">
                                <p class="text-sm text-blue-700">
                                    例如，输入：weight = [1, 3, 4], value = [15, 20, 30], w = 4
                                    输出：35（选择第 1 和第 3 件物品）
                                </p>
                            </div>
                        </div>
                    </div>
                </div>
            </div>

            <!-- Solution Approach -->
            <div class="bg-white rounded-xl shadow-md overflow-hidden mb-12 dp-card">
                <div class="p-6 md:p-8">
                    <div class="flex items-center mb-6">
                        <div class="w-12 h-12 bg-purple-100 rounded-full flex items-center justify-center mr-4">
                            <i class="fas fa-lightbulb text-purple-600 text-xl"></i>
                        </div>
                        <h2 class="text-2xl font-bold text-gray-800">解题思路</h2>
                    </div>
                    
                    <div class="grid md:grid-cols-2 gap-8 mb-8">
                        <div>
                            <h3 class="text-lg font-semibold text-gray-800 mb-3 flex items-center">
                                <i class="fas fa-project-diagram mr-2 text-purple-500"></i>
                                动态规划原理
                            </h3>
                            <p class="text-gray-700 mb-4 leading-relaxed">
                                定义 <span class="font-mono bg-gray-100 px-2 py-1 rounded">dp[i][j]</span> 表示从前 <span class="font-bold">i</span> 件物品中选择放入重量为 <span class="font-bold">j</span> 的背包中所获得的最大价值。
                            </p>
                            <p class="text-gray-700 leading-relaxed">
                                对于每件物品，我们有两种选择：放入背包或不放入背包。我们需要比较这两种选择的价值，取较大者作为当前状态的最优解。
                            </p>
                        </div>
                        <div>
                            <h3 class="text-lg font-semibold text-gray-800 mb-3 flex items-center">
                                <i class="fas fa-calculator mr-2 text-purple-500"></i>
                                状态转移方程
                            </h3>
                            <div class="bg-gray-100 p-4 rounded-lg">
                                <div class="text-gray-800 font-mono mb-2">
                                    dp[i][j] = max(不放入, 放入)
                                </div>
                                <div class="text-gray-800 font-mono">
                                    = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])
                                </div>
                            </div>
                        </div>
                    </div>

                    <div class="mb-6">
                        <h3 class="text-lg font-semibold text-gray-800 mb-3 flex items-center">
                            <i class="fas fa-wrench mr-2 text-purple-500"></i>
                            优化技巧
                        </h3>
                        <p class="text-gray-700 mb-4 leading-relaxed">
                            我们可以将二维数组优化为一维数组，将空间复杂度从 <span class="font-mono bg-gray-100 px-2 py-1 rounded">O(n*w)</span> 降低到 <span class="font-mono bg-gray-100 px-2 py-1 rounded">O(w)</span>。
                            关键点是在内层循环中逆向遍历背包容量，防止物品被重复计算。
                        </p>
                    </div>
                </div>
            </div>

            <!-- Visualization -->
            <div class="bg-white rounded-xl shadow-md overflow-hidden mb-12 dp-card">
                <div class="p-6 md:p-8">
                    <div class="flex items-center mb-6">
                        <div class="w-12 h-12 bg-green-100 rounded-full flex items-center justify-center mr-4">
                            <i class="fas fa-chart-bar text-green-600 text-xl"></i>
                        </div>
                        <h2 class="text-2xl font-bold text-gray-800">算法可视化</h2>
                    </div>
                    
                    <div class="relative bg-gray-50 p-6 rounded-lg border border-gray-200">
                        <div class="absolute top-0 right-0 m-4 flex space-x-2">
                            <span class="px-2 py-1 bg-blue-100 text-blue-800 text-xs font-medium rounded">物品1</span>
                            <span class="px-2 py-1 bg-green-100 text-green-800 text-xs font-medium rounded">物品2</span>
                            <span class="px-2 py-1 bg-purple-100 text-purple-800 text-xs font-medium rounded">物品3</span>
                        </div>
                        
                        <div class="grid grid-cols-1 md:grid-cols-2 gap-6">
                            <div>
                                <div class="flex items-center justify-between mb-2">
                                    <h4 class="font-semibold text-gray-700">背包容量</h4>
                                    <span class="text-xs text-gray-500">0 → 4</span>
                                </div>
                                <div class="bg-white p-4 rounded-lg shadow-inner border border-gray-200">
                                    <div class="h-64 overflow-auto">
                                        <div class="flex mb-1">
                                            <div class="w-16 text-xs text-gray-500 flex-shrink-0">0</div>
                                            <div class="flex-1 flex">
                                                <div class="h-6 bg-blue-100 mr-1" style="width: 0%"></div>
                                                <div class="h-6 bg-green-100 mr-1" style="width: 0%"></div>
                                                <div class="h-6 bg-purple-100" style="width: 0%"></div>
                                            </div>
                                        </div>
                                        <div class="flex mb-1">
                                            <div class="w-16 text-xs text-gray-500 flex-shrink-0">1</div>
                                            <div class="flex-1 flex">
                                                <div class="h-6 bg-blue-100 mr-1" style="width: 100%"></div>
                                                <div class="h-6 bg-green-100 mr-1" style="width: 0%"></div>
                                                <div class="h-6 bg-purple-100" style="width: 0%"></div>
                                            </div>
                                        </div>
                                        <div class="flex mb-1">
                                            <div class="w-16 text-xs text-gray-500 flex-shrink-0">2</div>
                                            <div class="flex-1 flex">
                                                <div class="h-6 bg-blue-100 mr-1" style="width: 100%"></div>
                                                <div class="h-6 bg-green-100 mr-1" style="width: 0%"></div>
                                                <div class="h-6 bg-purple-100" style="width: 0%"></div>
                                            </div>
                                        </div>
                                        <div class="flex mb-1">
                                            <div class="w-16 text-xs text-gray-500 flex-shrink-0">3</div>
                                            <div class="flex-1 flex">
                                                <div class="h-6 bg-blue-100 mr-1" style="width: 100%"></div>
                                                <div class="h-6 bg-green-100 mr-1" style="width: 100%"></div>
                                                <div class="h-6 bg-purple-100" style="width: 0%"></div>
                                            </div>
                                        </div>
                                        <div class="flex">
                                            <div class="w-16 text-xs text-gray-500 flex-shrink-0">4</div>
                                            <div class="flex-1 flex">
                                                <div class="h-6 bg-blue-100 mr-1" style="width: 100%"></div>
                                                <div class="h-6 bg-green-100 mr-1" style="width: 100%"></div>
                                                <div class="h-6 bg-purple-100" style="width: 100%"></div>
                                            </div>
                                        </div>
                                    </div>
                                </div>
                            </div>
                            <div>
                                <h4 class="font-semibold text-gray-700 mb-2">最优解路径</h4>
                                <div class="bg-white p-4 rounded-lg shadow-inner border border-gray-200 h-64 flex items-center justify-center">
                                    <div class="text-center">
                                        <div class="inline-block p-6 bg-blue-50 rounded-lg">
                                            <div class="flex items-center justify-center mb-4">
                                                <div class="w-10 h-10 rounded-full bg-blue-100 flex items-center justify-center mr-3">
                                                    <i class="fas fa-box text-blue-500"></i>
                                                </div>
                                                <div class="text-left">
                                                    <div class="font-semibold">物品1 + 物品3</div>
                                                    <div class="text-sm text-gray-600">重量: 1+4=5 ≤ 4? 否</div>
                                                </div>
                                            </div>
                                            <div class="flex items-center justify-center">
                                                <div class="w-10 h-10 rounded-full bg-blue-100 flex items-center justify-center mr-3">
                                                    <i class="fas fa-box-open text-blue-500"></i>
                                                </div>
                                                <div class="text-left">
                                                    <div class="font-semibold">物品1 + 物品2</div>
                                                    <div class="text-sm text-gray-600">重量: 1+3=4 ≤ 4? 是</div>
                                                </div>
                                            </div>
                                        </div>
                                    </div>
                                </div>
                            </div>
                        </div>
                    </div>
                </div>
            </div>

            <!-- Code Implementation -->
            <div class="bg-white rounded-xl shadow-md overflow-hidden mb-12 dp-card">
                <div class="p-6 md:p-8">
                    <div class="flex items-center mb-6">
                        <div class="w-12 h-12 bg-orange-100 rounded-full flex items-center justify-center mr-4">
                            <i class="fas fa-code text-orange-600 text-xl"></i>
                        </div>
                        <h2 class="text-2xl font-bold text-gray-800">代码实现</h2>
                    </div>
                    
                    <div class="mb-4">
                        <div class="flex items-center mb-2">
                            <i class="fas fa-laptop-code text-orange-500 mr-2"></i>
                            <span class="font-medium">Java实现（一维数组优化版）</span>
                        </div>
                        <div class="code-block p-4 rounded-lg overflow-x-auto">
                            <pre class="text-sm"><code>public int knapsack(int[] weight, int[] value, int w) {
    // 获取物品数量
    int n = weight.length;
    
    // 创建一维动态规划数组，表示背包容量为j时的最大价值
    int[] dp = new int[w + 1];
    
    // 遍历每件物品
    for (int i = 0; i &lt; n; i++) {
        // 从背包容量w开始，倒序遍历到当前物品的重量
        // 必须倒序遍历，防止物品被重复添加
        for (int j = w; j &gt;= weight[i]; j--) {
            // 比较不放入当前物品和放入当前物品的价值大小
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    
    // 返回背包容量为w时的最大价值
    return dp[w];
}</code></pre>
                        </div>
                    </div>
                </div>
            </div>

            <!-- Key Takeaways -->
            <div class="bg-white rounded-xl shadow-md overflow-hidden">
                <div class="p-6 md:p-8">
                    <div class="flex items-center mb-6">
                        <div class="w-12 h-12 bg-indigo-100 rounded-full flex items-center justify-center mr-4">
                            <i class="fas fa-key text-indigo-600 text-xl"></i>
                        </div>
                        <h2 class="text-2xl font-bold text-gray-800">核心要点</h2>
                    </div>
                    
                    <div class="grid md:grid-cols-2 gap-6">
                        <div class="bg-indigo-50 p-6 rounded-lg">
                            <h3 class="font-semibold text-indigo-800 mb-3 flex items-center">
                                <i class="fas fa-check-circle mr-2"></i>
                                算法特性
                            </h3>
                            <ul class="text-gray-700 space-y-2">
                                <li class="flex items-start">
                                    <i class="fas fa-angle-right text-indigo-500 mt-1 mr-2 text-xs"></i>
                                    <span>时间复杂度: O(n*w)</span>
                                </li>
                                <li class="flex items-start">
                                    <i class="fas fa-angle-right text-indigo-500 mt-1 mr-2 text-xs"></i>
                                    <span>空间复杂度: O(w)</span>
                                </li>
                                <li class="flex items-start">
                                    <i class="fas fa-angle-right text-indigo-500 mt-1 mr-2 text-xs"></i>
                                    <span>适用于物品数量不多，背包容量合理的场景</span>
                                </li>
                            </ul>
                        </div>
                        <div class="bg-indigo-50 p-6 rounded-lg">
                            <h3 class="font-semibold text-indigo-800 mb-3 flex items-center">
                                <i class="fas fa-lightbulb mr-2"></i>
                                应用场景
                            </h3>
                            <ul class="text-gray-700 space-y-2">
                                <li class="flex items-start">
                                    <i class="fas fa-angle-right text-indigo-500 mt-1 mr-2 text-xs"></i>
                                    <span>资源分配问题</span>
                                </li>
                                <li class="flex items-start">
                                    <i class="fas fa-angle-right text-indigo-500 mt-1 mr-2 text-xs"></i>
                                    <span>投资组合优化</span>
                                </li>
                                <li class="flex items-start">
                                    <i class="fas fa-angle-right text-indigo-500 mt-1 mr-2 text-xs"></i>
                                    <span>任务调度</span>
                                </li>
                            </ul>
                        </div>
                    </div>
                </div>
            </div>
        </div>
    </section>
</body>
</html>